package algorithm.middle;


import pojo.TreeNode;

/**
 * 给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。
 * <p>
 * 返回移除了所有不包含 1 的子树的原二叉树。
 * <p>
 * 节点 node 的子树为 node 本身加上所有 node 的后代。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/binary-tree-pruning
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class PruneTree814 {

    public TreeNode pruneTree(TreeNode root) {
        fun(root);
        return root.val==-1?null:root;
    }

    //后续遍历
    //剪枝
    public void fun(TreeNode root) {
        if (root.left != null) {
            fun(root.left);
        }
        if (root.right != null) {
            fun(root.right);
        }
        if (root.left != null && root.left.val == -1) {
            root.left = null;
        }
        if (root.right != null && root.right.val == -1) {
            root.right = null;
        }
        if (root.left == null && root.right == null && root.val == 0) {
            root.val = -1;
        }
    }

    //递归
    public TreeNode pruneTree2(TreeNode root) {
        if (root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left != null || root.right != null) return root;
        return root.val == 0 ? null : root;
    }

}
